﻿using System;
using System.Collections.Generic;
using System.Linq;
using System.Text;
using System.Threading.Tasks;

namespace SubAlgorithm.Inter_704_Search
{
    class MainProject
    {
        /// <summary>
        /// 二分查找
        /// </summary>
        /// <param name="args"></param>
        static void Main(string[] args)
        {
            int[] vs = new int[] { 1, 2, 3, 4, 5, 6, 7, 8, 9 };
            int[] vs2 = new int[] {-1, 0, 3, 5, 9, 12 };
            Console.WriteLine(Search(vs2, 6));
            Console.ReadKey();
        }

        /// <summary>
        /// 二分查找
        /// </summary>
        /// <param name="nums"></param>
        /// <param name="target"></param>
        /// <returns></returns>
        public static int Search(int[] nums, int target)
        {
            int lastIndex = 0; 
            int nextIndex = nums.Length-1;

            int curValueIndex = 0;

            while (lastIndex<= nextIndex)
            {
                curValueIndex = (lastIndex + nextIndex+1) / 2;
                if (nums[curValueIndex] > target)
                {
                    nextIndex = curValueIndex-1;
                }
                else if (nums[curValueIndex] < target)
                {
                    lastIndex = curValueIndex+1;
                }
                else
                {
                    return curValueIndex;
                }
            }
            return -1;
        }
    }

}
